package com.future;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * Description:
 * https://leetcode-cn.com/problems/permutations-ii/
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 * @author weiruibai.vendor
 * Date: 2022/2/19 19:50
 */
public class Solution_permuteUnique_47 {

    public static void main(String[] args) {

        Set<List<Integer>> set = new HashSet<List<Integer>>();
        List<Integer> l1 = new ArrayList<Integer>() {{
            add(1);
            add(2);
            add(3);
        }};
        List<Integer> l2 = new ArrayList<Integer>() {{
            add(1);
            add(2);
            add(3);
        }};
        set.add(l1);
        set.add(l2);

        int[] nums = {1};
        List<List<Integer>> lists = permuteUnique(nums);

        print(lists);
    }

    private static void print(List<List<Integer>> lists) {
        for (int i = 0; i < lists.size(); i++) {
            System.out.println(Arrays.asList(lists.get(i)));
        }
    }

    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null) {
            return ans;
        }
        if (nums.length == 1) {
            ans.add(new ArrayList<Integer>() {{
                add(nums[0]);
            }});
            return ans;
        }
        List<Integer> list = new ArrayList<>();
        for (Integer nu : nums) {
            list.add(nu);
        }

        process(list, ans, new ArrayList<Integer>());
        Set<List<Integer>> set = new HashSet<List<Integer>>();
        set.addAll(ans);
        return set.stream().collect(Collectors.toList());
    }

    private static void process(List<Integer> rest, List<List<Integer>> ans, List<Integer> tmpAns) {
        if (rest.size() == 0) {
            // 需要重新创建对象，否则tmpAns不断add元素
            List<Integer> tmp = new ArrayList<>();
            tmp.addAll(tmpAns);
            ans.add(tmp);
            return;
        }
        int N = rest.size();
        for (int i = 0; i < N; i++) {
            int value = rest.get(i);
            rest.remove(i);
            tmpAns.add(value);
            process(rest, ans, tmpAns);
            // 移除最新加入的元素（末尾）
            tmpAns.remove(tmpAns.size() - 1);
            rest.add(i, value);
        }
    }


}
